/**
 * 
 */
package stack2;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 * @author michaelyi
 *
 */
public class ExpressionEvaluation {

	/**
	 * Evaluate Reverse Polish Notation
	 * Evaluate the value of an arithmetic expression in Reverse Polish Notation.
	 *	
	 * Valid operators are +, -, *, /. Each operand may be an integer or another expression.
	 * Some examples:
		  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
		  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
	 */
	
	private Set<String> operators = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
	
	private int eval(int val1, int val2, char operator) {
		int result = 0;
		switch (operator) {
		case '+': result = val1 + val2;
		break;
		case '-': result = val1 - val2;
		break;
		case '*': result = val1 * val2;
		break;
		case '/': result = val1 / val2;
		break;
		}
		
		return result;
	}
	
    public int evalRPN(String[] tokens) throws Exception{
    	Stack<Integer> stack = new Stack<>();
    	for (String token : tokens) {
    		if (!operators.contains(token)) {
    			stack.push(Integer.parseInt(token));
    		}
    		else {
    			char operator = token.charAt(0);
    			if (stack.size() < 2) {
					throw new Exception("invalid reverse polish notation!");
    			}
    			else {
        			int operand2 = stack.pop();
        			int operand1 = stack.pop();
    				stack.push(eval(operand1, operand2, operator));
    			}
    			
    		}
    	}
        
    	return stack.pop();
    }
	
    
    
   /**
	Input an arithmetic expression with ONLY +, -, * and /, parse the expression and calculate the result.
	Input: 5.6 / 0.7 * 2 – 3.5& X; H7 x& k& `* Z+ ^4 \) w
	Output: 12.5* B$ y' O4 a2 U$ r
	Input: -1.3 + 5.1 / 3 – 0.8, Z$ {! W/ a, z  ~( @- \
	Output: -0.4
	1.一个stack的方法。也就是楼主说的要先转换成 波兰表达式，然后通过一个stack计算，但是转换的这个步骤比较麻烦
	2.两个stack，一个存符号，一个存数字 (这个比较简单，适合面试)
	3.两个while直接计算。
    */
    static Map<Character, Integer> precedence = null;
    static {
    	precedence = new HashMap<>();
    	precedence.put('+', 0);
    	precedence.put('-', 0);
    	precedence.put('*', 0);
    	precedence.put('/', 0);
    	
    }
    public static double eval() {
    	Stack<Character> operators = new Stack<>();
    	Stack<Double> operands = new Stack<>();
    	
    	
    	return 0;
    }
    
	public double eval(double val1, double val2, char operator) {
		double result = 0;
		switch (operator) {
		case '+': result = val1 + val2;
		break;
		case '-': result = val1 - val2;
		break;
		case '*': result = val1 * val2;
		break;
		case '/': result = val1 / val2;
		break;
		}
		
		return result;
	}
	
    /**
 	Input an arithmetic expression with Include (, ), +, -, * and /, parse the expression and calculate the result.
 	Input: 5.6 / 0.7 * 2 – 3.5& X; H7 x& k& `* Z+ ^4 \) w
 	Output: 12.5* B$ y' O4 a2 U$ r
 	Input: -1.3 + 5.1 / 3 – 0.8, Z$ {! W/ a, z  ~( @- \
 	Output: -0.4
 	1.一个stack的方法。也就是楼主说的要先转换成 波兰表达式，然后通过一个stack计算，但是转换的这个步骤比较麻烦
     */
	public static double evalInfix(String infix) {
		assert(infix != null && !infix.equals(" "));
		
		double result = 0;
		try {
			result = evaluatePostfix(convertToPostfix(infix));
		}
		catch (Exception e) {
			e.printStackTrace();
		}
		
		return result;
	}

	public static double evaluatePostfix(List<Object> postfixTokens) throws Exception {
		assert(postfixTokens != null &&  !postfixTokens.isEmpty());
		
		Stack<Operand> operands = new Stack<Operand>();
		for (Object token : postfixTokens) {
			if (token instanceof Operand) {
				operands.push((Operand)token);
			}
			else if (token instanceof Operator) {
				Operator operator = (Operator)token;
				if (operands.size() >= 2) {
					Operand operand2 = operands.pop();
					Operand operand1 = operands.pop();
					operands.push( new Operand( operator.eval(operand1.value, operand2.value) ) );
				}
				else {
					throw new Exception("invalid reverse polish notation!");
				}
			}
		}
		
		return operands.pop().value;
	}
	
	public static List<Object> convertToPostfix(String infix) {
		assert(infix != null && !infix.equals(" "));
		
		List<Object> postfixTokens = new LinkedList<Object>();
		Stack<Operator> operators = new Stack<Operator>();
		List<Object> infixTokens = string2Tokens(infix);
		for (Object token : infixTokens) {
			if (token instanceof Operand) {
				postfixTokens.add(token);
			}
			else if (token instanceof Operator) {
				Operator operator = (Operator)token;
				switch (operator) {
				case LEFT_PARENTHESIS:
					operators.push(operator);
					break;
				case RIGHT_PARENTHESIS:
					while (operators.peek() != Operator.LEFT_PARENTHESIS) {
						postfixTokens.add(operators.pop());
					}
					operators.pop();
					break;
				default:
					while (!operators.isEmpty() &&
							operators.peek().precedence() >= operator.precedence() &&
							operators.peek() != Operator.LEFT_PARENTHESIS) {
						postfixTokens.add(operators.pop());
					}
					operators.push(operator);
				}
			}
		}// end of for
		
		while (!operators.isEmpty()) {
			postfixTokens.add(operators.pop());
		}
		
		return postfixTokens;
	}
	
	private static List<Object> string2Tokens(String expression) {
		assert(expression != null && !expression.equals(" "));
		List<Object> tokens = new LinkedList<Object>();  
		for (int i = 0, size = expression.length(); i < size;) {
			int j = i + 1;
			String ch = expression.substring(i, j);
			if (ch.matches("^[\\+\\-\\*/%\\^\\(\\)]$")) {
				tokens.add(Operator.getOperator(ch));
				++i;
			}
			else {
				// double or int 
				// ^[-+]?([0-9]*\.[0-9]+|[0-9]+)$
				// ^([0-9]*\\.?[0-9]*|[0-9]+)$
				// ^[-+]?[0-9]*\.?[0-9]+$
				while (ch.matches("^([0-9]*\\.?[0-9]*)$") && j++ < size)	{
					ch = expression.substring(i, j);
				}
				tokens.add(
						new Operand( 
								Double.valueOf(
												expression.substring(i, j-1) 
											  ).doubleValue() 
									)
						);
				i = j - 1;
			}
		}
		
		for (Object o : tokens) {
			System.out.printf("%s,", o.toString());
		}
		
		return tokens;
	}
	
	/**
	 * Construct
	 */
	public ExpressionEvaluation() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println("Evaluation Infix Expression!");
		String infix = ".3*(2.3+3.3)^2%2/3.14";
		double result = evalInfix(infix);
		System.out.printf("infix: \"%s\" = %f", infix, result);
	}

}

class Operand {
	public double value;
	public Operand(double v) {
		value = v;
	}
	
	@Override
	public String toString() { return String.valueOf(value); }
}

enum Operator {
	ADDITION {
		public double eval(double a, double b) { return a + b; }
		
		@Override
		public String toString() { return "+"; }
		
	}, 
	
	SUBSTRUCTION {
		public double eval(double a, double b) { return a - b; }
		
		@Override
		public String toString() { return "-"; }
	}, 
	
	MULTIPLICATION {
		public double eval(double a, double b) { return a * b; }
		
		@Override
		public String toString() { return "*"; }
	}, 
	
	DIVISION {
		public double eval(double a, double b) { return a / b; }
		
		@Override
		public String toString() { return "/"; }
	}, 
	
	RESIDUE {
		public double eval(double a, double b) { return a % b; }
		
		@Override
		public String toString() { return "%"; }
	}, 
	
	POWER {
		public double eval(double a, double b) { return Math.pow(a, b); }
		
		@Override
		public String toString() { return "^"; }
	}, 
	
	LEFT_PARENTHESIS {
		public double eval(double a, double b) { throw new UnsupportedOperationException(); }
		
		@Override
		public String toString() { return "("; }
	}, 
	
	RIGHT_PARENTHESIS {
		public double eval(double a, double b) { throw new UnsupportedOperationException(); }
		
		@Override
		public String toString() { return ")"; }
	};
	
	public abstract double eval(double a, double b) throws Exception;


	// switch is not recommended.
	public int precedence() {
		int priority = 0;
		switch (this) {
		case ADDITION:
			priority = 40;
			break;
		case SUBSTRUCTION:
			priority = 40;
			break;
		case RESIDUE:
			priority = 70;
			break;
		case MULTIPLICATION:
			priority = 70;
			break;
		case DIVISION:
			priority = 70;
			break;
		case POWER:
			priority = 100;
			break;
		case LEFT_PARENTHESIS:
		case RIGHT_PARENTHESIS:
			priority = 100;
			break;
		default:
			throw new AssertionError("Unknown operation: " + this);
		}
		
		return priority;
	}
	
	public static Operator getOperator(String s) {
		assert(s != null && !s.equals(" "));
		
		Operator opt = null;
		if (s.equals(ADDITION.toString()))
			opt = ADDITION;
		else if (s.equals(SUBSTRUCTION.toString()))
			opt = SUBSTRUCTION;
		else if (s.equals(MULTIPLICATION.toString()))
			opt = MULTIPLICATION;
		else if (s.equals(DIVISION.toString()))
			opt = DIVISION;
		else if (s.equals(RESIDUE.toString()))
			opt = RESIDUE;
		else if (s.equals(POWER.toString()))
			opt = POWER;
		else if (s.equals(LEFT_PARENTHESIS.toString()))
			opt = LEFT_PARENTHESIS;		
		else if (s.equals(RIGHT_PARENTHESIS.toString()))
			opt = RIGHT_PARENTHESIS;
		else
			throw new AssertionError("Unknow op: " + s);
		
		return opt;
	}
}


